// ml:run = time -p $bin < input
// ml:opt = 0
// ml:ccf += -g
#include <iostream>
#include <bitset>
#include <cstring>
#include <vector>

using ll = long long;
std::vector<std::vector<int>> g;
int const maxn = 200;
int suffix[maxn][maxn];
int in[maxn];
int n, m, s;
ll ans;
std::bitset<101> bg[maxn];

void init()
{
    ans = 0;
    g.clear();
    g.resize(n + 1);
    for (int i = 0; i < maxn; i++) bg[i].reset();
    memset(in, 0, sizeof(in));
    memset(suffix, 0, sizeof(suffix));
}

void add_edge(int u, int v)
{
    g[u].push_back(v);
    g[v].push_back(u);
    bg[u][v] = true;
    bg[v][u] = true;
    in[u]++; in[v]++;
}

void dfs(int deep, int last, std::bitset<101> st, std::bitset<101> extend)
{
    if (deep == s) {
        ans++;
        return;
    }
    if (n - last < s - deep) return;
    for (auto i : g[last]) {
        if (i <= last) continue;
        if (suffix[i][last + 1] < n - deep - 1) continue;
        if (!extend[i]) continue;
        if (!deep || (bg[i] & st).any()) {
            st[i] = true;
            dfs(deep + 1, i, st, extend & bg[i]);
            st[i] = false;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    int T; std::cin >> T;
    while (T--) {
        std::cin >> n >> m >> s;
        init();
        for (int i = 0; i < m; i++) {
            int u, v; std::cin >> u >> v;
            add_edge(u, v);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = n; j >= 0; j--)
                suffix[i][j] = suffix[i][j + 1] + bg[i][j];
        }

        for (int i = 1; i <= n; i++)
            if (in[i] >= s - 1) g[0].push_back(i);
            /* g[0].push_back(i); */
        std::bitset<101> tmp;
        std::bitset<101> ex;
        ex.set();
        tmp.reset();
        dfs(0, 0, tmp, ex);

        std::cout << ans << "\n";
    }
}

